<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8" />
  <meta http-equiv="X-UA-Compatible" content="IE=edge" />
  <meta name="viewport" content="width=device-width, initial-scale=1.0" />
  <title>插入排序</title>
</head>

<body>

</body>
<script>
  // 插入排序：
  // 和打牌差不多，一开始先抓一张牌，
  // 然后继续抓牌，将新牌与手里的牌进行比较（从前往后比），
  // 找到第一个比他小的值，小就放在他前面，反之就插到最后面

  function insert(arr) {
    // 1. 准备一个新数组，用来存储抓到手里的牌，开始先抓一张牌
    let handle = [arr[0]]
    // 2.从第二项开始依次抓牌，一直到把台面上的牌抓光
    for (let i = 1; i < arr.length; i++) {
      // A 是新抓的牌
      let A = arr[i]
      let insert = false
      // 和 handle 手里的牌进行比较（从前向后）
      for (let j = 0; j < handle.length; j++) {
        // 每一次要比较的手里的牌
        let B = handle[j]
        // 从前往后查找，查找第一个比新牌小的旧牌，将新牌插入到旧牌前面
        if (A < B) {
          insert = true
          handle.splice(j, 0, A)
          break
        }
      }
      if (!insert) {
        handle.push(A)
      }
    }
    return handle
  }


  let arr = [12, 5, 20, 3, 66]
  arr = insert(arr)
  console.log(arr);

</script>

</html>